package february.test_2_1;

import java.util.Deque;
import java.util.LinkedList;

public class TestMain3 {
    int n = 1;
    public int getLCA(int a, int b) {
        // write code here
        return A(n,a,b);
    }
    public Boolean B(int n,int p,Deque<Integer> stack) {
        if(n > p) {
            return false;
        }
        stack.push(n);
        if(n == p) {
            return true;
        }
        boolean ret1 = B(2*n,p,stack);
        if(ret1) {
            return true;
        }
        boolean ret2 = B(2 * n + 1,p,stack);
        if(ret2) {
            return true;
        }
        stack.pop();
        return false;
    }
    public int A(int n,int a,int b) {
        Deque<Integer> stack1 = new LinkedList<>();
        B(n,a,stack1);
        Deque<Integer> stack2 = new LinkedList<>();
        B(n,b,stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2) {
            int size = size1 - size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
        } else {
            int size = size2 - size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }
        }
        while (!stack1.isEmpty()&&!stack2.isEmpty()) {
            if(stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            } else {
                return stack1.peek();
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        TestMain3 testMain3 = new TestMain3();
        System.out.println(testMain3.getLCA(4, 5));
    }
}
